UC知道加分请教一个简单"数据结构算法"问题
来源：百度知道 编辑：UC知道 时间：2024/05/03 16:04:24
This C program has somg small wrongs,please point out for me! Thank you !!!
main()
{
int a[6]={1,2,3,4,5,6};
int key,mid,low,high,flat;
low=0;
flat=0;
high=5;
key=0;
mid=(low+high)/2;
scanf("%d",&key);
while(low<=high&&!flat)
{
mid=(low+high)/2;
if(a[mid]==key)
{
flat=1;
printf("Found\n");
}
else if(a[mid]>key)
high=mid;
else if(a[mid]<key)
low=mid;
}
}
在这个算法中,没法查找到6这个元素,你可以试一下
main()
{
int a[6]={1,2,3,4,5,6};
int key,mid,low,high,flat;
low=0;
flat=0;
high=5;
key=0;
mid=(low+high)/2;
scanf("%d",&key);
while(low<=high&&!flat)
{
mid=(low+high)/2;
if(a[mid]==key)
{
flat=1;
printf("Found\n");
}
else if(a[mid]>key)
high=mid;
else if(a[mid]<key)
low=mid;
}
}
在这个算法中,没法查找到6这个元素,你可以试一下
把倒数第3行改成:
low=mid+1;
可以把倒数第5行改成:
high=mid-1;
如果不加的话,你的程序应该一直找不到6的,因为(4+5)/2=4,你的mid永远不能等于5,也就是说永远也不会跟a[5]进行比较,从而导致死循环.
修改倒数第3行是为了解决死循环的致命错误,而修改倒数第5行可以认为是对程序执行效率的一种改进,不会影响程序的正确性.
将high=5;改成high=6;